487D - Conveyor Belts - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int maxLig = (1e5) + 5;
const int maxCol = 12;
const int maxReq = (1e5) + 5;
const int sqr = 400;
int nbLig, nbCol, nbReq;
char grille[maxLig][maxCol];
int proc[maxLig][maxCol];
int tps = 0;
pair<int, int> go[maxLig][maxCol];
void comp(int lig, int col, int safeLig) {
  if (proc[lig][col] == tps)
    return;
  proc[lig][col] = tps;
  int nextLig = lig, nextCol = col;
  if (grille[lig][col] == '<')
    --nextCol;
  else if (grille[lig][col] == '>')
    ++nextCol;
  else if (grille[lig][col] == '^')
    --nextLig;
  if (nextLig == safeLig || grille[nextLig][nextCol] == '~') {
    go[lig][col] = {nextLig, nextCol};
  } else if (grille[lig][col] != '^' && grille[lig][nextCol] != '^' &&
             grille[lig][col] != grille[lig][nextCol]) {
    go[lig][col] = {0, 0};
  } else {
    comp(nextLig, nextCol, safeLig);
    go[lig][col] = go[nextLig][nextCol];
  }
}
pair<int, int> getFin(int lig, int col) {
  while (grille[lig][col] != '~') {
    pii e = go[lig][col];
    lig = e.first;
    col = e.second;
  }
  return {lig, col};
}
int blocRef[maxLig];
bool compBloc(int bloc) {
  int deb = bloc * sqr, fin = min(nbLig, (bloc + 1) * sqr);
  if (deb > nbLig)
    return false;
  for (int lig = deb + 1; lig <= fin; ++lig) {
    blocRef[lig] = bloc;
    for (int col = 1; col <= nbCol; ++col) {
      comp(lig, col, deb);
    }
  }
  return true;
}
int main() {
  cin >> nbLig >> nbCol >> nbReq;
  fill_n(&grille[0][0], maxLig * maxCol, '~');
  for (int lig = 1; lig <= nbLig; ++lig) {
    for (int col = 1; col <= nbCol; ++col) {
      cin >> grille[lig][col];
    }
  }
  ++tps;
  for (int bloc = 0;; ++bloc) {
    if (!compBloc(bloc))
      break;
  }
  for (int req = 0; req < nbReq; ++req) {
    char mode;
    cin >> mode;
    int lig, col;
    cin >> lig >> col;
    if (mode == 'A') {
      pii res = getFin(lig, col);
      if (res == pii{0, 0})
        res = {-1, -1};
      cout << res.first << " " << res.second << "\n";
    } else {
      ++tps;
      char nv;
      cin >> nv;
      grille[lig][col] = nv;
      int bloc = blocRef[lig];
      compBloc(bloc);
      if (bloc)
        compBloc(bloc - 1);
    }
  }
}

// ohKHyHNWJqQOsdLaVjCXqrgrtgeeGlVjqeBRIUtHqjBCZyHUwkylApbHpAgdsjWoTerbmBfsNtJTPoEwvZvayATadUCQiGgZosxFBSpFLvMChaPlxAupVlTdnKmwanhN